The present invention relates generally to communication systems, and specifically, to a method and apparatus for smoothing the rate of packet discards for random early detection in a communication device.
Asynchronous Transfer Mode (xe2x80x9cATMxe2x80x9d) networks are cell switching networks that transfer fixed length data units called xe2x80x9ccells.xe2x80x9d Cells are transmitted from a source node to a destination node through ATM (or digital) switches, which are coupled together by way of communication lines. An ATM switch includes a plurality of input ports coupled to input communication lines and a plurality of output ports coupled to output communication lines.
Cells carry voice, video, and data information from the source node to the destination node. Cells are fifty-three bytes in length and include five bytes of header information and forty-eight bytes of payload. The header information includes a virtual path identifier (xe2x80x9cVPIxe2x80x9d) field and a virtual channel identifier (xe2x80x9cVCIxe2x80x9d) field, identifying the next destination of a cell as it passes through a series of ATM switches on its way to its destination node. ATM switches asynchronously receive cells on the input ports and switch the cells to the proper output ports based on the VPI and VCI information in the header of the cells.
Each communication line can carry several different connections simultaneously. Queues are typically used within an ATM switch for temporarily storing cells prior to transmission on a communication line. More than one queue may be used to service different types of class of service connections. For example, cells belonging to higher priority connections (e.g., voice connections) may be stored in queues that are marked as higher priority. On the other hand, cells belonging to lower priority connections (e.g., data) may be stored in queues that are marked as lower priority.
These queues, which have a finite size, must be able to store cells for each connection. Thus, in an ATM switch architecture, it is essential to efficiently use buffer resources, while remaining fair to all connections. Moreover, since queues have a finite size, threshold values are assigned to the queues to define a maximum number of cells that can be stored for each connection. Consequently, one function of an ATM switch is to determine whether to accept or reject cells depending on whether the queue that the cell belongs to has reached its maximum threshold.
The ATM Adaptation Layer (xe2x80x9cAALxe2x80x9d) is utilized to segment higher layer packets into cells for transporting Transmission Control Protocol/Internet Protocol (xe2x80x9cTCP/IPxe2x80x9d) traffic over ATM networks. If a cell is discarded by an ATM switch, the entire packet that the cell belongs to is dropped. If TCP/IP packets from several sources are dropped at substantially the same time, a global synchronization problem is likely to occur. Global synchronization occurs when source nodes react to dropped packets synchronously, slowing retransmission of packets. When the source nodes determine that the network is not congested, they begin to retransmit packets at a higher rate, thereby causing congestion again. This type of oscillating behavior reduces throughput.
One technique for solving TCP global synchronization has been proposed by Sally Floyd and Van Jacobson, entitled xe2x80x9cRandom Early Detection Gateways for Congestion Avoidancexe2x80x9d, published in August 1993 by IEEE/ACM Transactions on Networking. According to Floyd/Jacobson, a random early detection (xe2x80x9cREDxe2x80x9d) algorithm is employed to smooth the distribution of cell discards over time, thereby reducing TCP global synchronization and improving performance.
However, RED is not well suited in high-speed implementations in hardware since it requires multiplication and division operations. Prior art techniques may have performed the multiplication/division smoothing function of RED in software, or used a look-up table in hardware, which is either expensive in terms of chip die area or has limited precision.
A method for smoothing a rate of cell discards for random early detection in a communication device is described. A cell is detected and an instantaneous discard probability is calculated. The method includes updating a discard probability as a function of the instantaneous discard probability and an accumulated probability, and comparing the discard probability with a random number. If the discard probability is greater than the random number, the cell is discarded, otherwise the cell is accepted.
Other objects, features, and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below.